搜尋此網誌

2011年7月18日 星期一

Queue Implemented by a Linked List

Queue:是一種先進先出的資料結構(First In First Out).
下面的範例程式使用C++ 的Linked List來實現Queue.




#include <iostream>
using namespace std;

class Node {

public:
int data;
Node* nxtNode;
Node(int _data) {
data=_data;//Data
nxtNode=NULL;//pointer to next one
}
};

class LinkedList {
Node* previous;
Node* next;
public:
LinkedList() {
previous=NULL;
next=NULL;
}

void insert(Node * _node) {
if (previous==NULL) {
previous= next= _node;//first node
} else {
(*next).nxtNode=_node;
next=_node;
}
}

void displayAll() {
Node* tmp=previous;
while(tmp!=NULL){
cout<<(*tmp).data <<endl;
tmp=(*tmp).nxtNode;
}
}
};

int main() {
Node* firstNode=new Node(1);
Node* secondNode=new Node(2);
Node* thirdNode=new Node(3);
LinkedList ll;
ll.insert(firstNode);
ll.insert(secondNode);
ll.insert(thirdNode);
ll.displayAll();
return 0;
}

Stack implementation linked list

以下所有的資料結構都是用C++實作,
    linked list
  • 用指標(pointer)實作的list可以無限制的擴充大小,但無法像陣列一樣可以直接(Direct)或是隨機存取(Random Access)儲存的資料.

  • 基本的linkeded list(鏈結串列),包含一個data的欄位,和一個next pointer欄位用來指向下一個資料


以下是以一個LinkedList實作Stack(First In Last Out)的例子