Stack and Queue

堆疊與佇列

堆疊（FILO）與佇列（FIFO）的基本性質
堆疊與佇列的實做使用陣列或鏈結
佇列的變形 – 環狀佇列
堆疊的應用：順序反轉、中序轉後序、圖形的DFS、副程式、遞迴
佇列的應用：排隊行為、工作排程、圖形中的BFS、I/O裝置佇列、系統效能模擬
前序、中序、後序互轉
利用堆疊把中序轉後序（陣列可以將順序顛倒）

以陣列表示stack演算法

item stack[N+1]; //stack[0]空間不使用,則可放N個元素,表1~N
int top=0;

void push(int x)
{
if (top==n)
print("stack is full");
else
stack[++top]=x;
}

int pop()
{
if (top==0)
print("stack is empty");
else
x=stack[top--];
return x;
}

以Linked-List表示stack演算法

typedef struct node *pointer;
struct node{
int data;
pointer link;
}

void push(int x)
{
pointer temp;
temp=(pointer)malloc(struct node);
temp->data=x; //temp->data=(*temp).data,記得*temp需加上括號
temp->link=top;
top=temp;
}

int pop()
{
pointer temp;
int x;
if (top==null)
print("stack is empty");
else
temp=top;
top=temp->link;
x=temp->data;
free(temp);
return x;
}

以Linked-List表示Queue演算法

typedef struct node *pointer;
struct node{
int data;
pointer next;
}
pointer Front,Rear;

void AddNode(x)
{
pointer temp;
temp=(pointer)malloc(struct node);
temp->data=x;
temp->next=null;
if (Rear=null) //表Queue是空的
Front=temp;
Rear=temp;
else
Rear->next=temp;
Rear=temp;
}

int DeleteNode()
{
pointer temp;
int x;
if (Front==null)
print("Queue is empty");
else
temp=Front;
Front=temp->next
x=temp->data;
free(temp);
return x;
}

ps:演算法多指虛擬碼(pseudo code)。