# Chap. 03 - Stack and Queue
> 課程內容 : 中興大學應用數學系 顏增昌教授 (111 學年度第 1 學期)
> 參考書目 : Fundamentals of Data Structures in C (2nd), Ellis H., Sartaj S., Susan A.-F.
>
>其他科目內容請參見 [[Here]](https://hackmd.io/@ChenZE/By4SOO6Jyl)
## Content
* [Sec. 3.1 Stack](#Sec-31-Stack)
* [1. Introduction to stack](#1-Introduction-to-stack)
* [2. ADT of stack](#2-ADT-of-stack)
* [3. Stack implement](#3-Stack-implement)
* [3.1 Implement of ADT](#31-Implement-of-ADT)
* [3.2 Stack implement](#32-Stack-implement)
* [Sec. 3.2 Dynamic stack](#Sec-32-Dynamic-stack)
* [1. Introduction to dynamic stack](#1-Introduction-to-dynamic-stack)
* [2. Memory allocation](#2-Memory-allocation)
* [3. Dynamic stack implement](#3-Dynamic-stack-implement)
* [3.1 Expand memory space](#31-Expand-memory-space)
* [3.2 Implement of dynamic stack](#32-Implement-of-dynamic-stack)
* [Sec. 3.3 Queue](#Sec-33-Queue)
* [1. Introduction to queue](#1-Introduction-to-queue)
* [2. ADT of queue](#2-ADT-of-queue)
* [3. Queue implement](#3-Queue-implement)
* [3.1 Implement of ADT](#31-Implement-of-ADT)
* [3.2 Implement of queue](#32-Implement-of-queue)
* [4. Application: job scheduler](#4-Application-job-scheduler)
* [5. Circular queue](#5-Circular-queue)
* [5.1 Implement of circular queue add and delete](#51-Implement-of-circular-queue-add-and-delete)
* [5.2 Implement of circular queue](#52-Implement-of-circular-queue)
* [Sec. 3.4 Dynamic queue](#Sec-34-Dynamic-queue)
* [1. Introduction to dynamic queue](#1-Introduction-to-dynamic-queue)
* [2. Implement of circular queue](#2-Implement-of-circular-queue)
* [2.1 Expand memory space](#21-Expand-memory-space)
* [2.2 Implement of dynamic queue](#22-Implement-of-dynamic-queue)
## Sec. 3.1 Stack
### 1. Introduction to stack
堆疊(stack)是一種**有序(ordered)的串列容器**。在 stack 中，元素的**插入(push)與刪除(pop)都是在 top 端完成**。
給定一個空的 stack S，初始狀態時 top 指標會指向 -1 表示 S 是一個空的 stack。將 A、B、C 三個元素依序 push 到 S 中可得
$$
S = \{A,\ B,\ C\}
$$
其中 C 稱為頂端元素，A 稱為底部元素。此時 top 會指向頂端的 C 元素。若再將元素 C 從 stack 中 pop 出去可得
$$
S = \{A,\ B\}
$$
此時 top 會指向頂端的 B 元素，具體過程如下圖所示。
從上述 stack 做 push 與 pop 的過程可以發現，**==最後添加的元素會最先被刪除==**，符合後進先出(**L**ast-**I**n-**F**irst-**O**ut, LIFO)的規則
### 2. ADT of stack
在 stack 的實作中，可以使用一個長度為 n 的一維陣列 `stack[n]` 來表示一個可存放 n 個元素的 stack。
* 底部元素放在 `stack[0]`，頂部元素放在 `stack[n-1]`
* 使用一個 `top` 變數來指向頂端的元素，若 `top = -1` 則表示為**空的 stack**
```
ADT of Stack
Object : A ordered list including zero or numerous items
Operation :
Stack CreateS(maxStackSize)::=
建立一個容量為 maxStackSize 的空的 stack
Boolean IsFull(stack, maxStackSize)::=
if (stack 的元素個數 == maxStackSize)
return True
else return False
Stack Push(stack, item)::=
if (IsFull(stack))
return stackfull
else 將 item 放在 stack 的頂端
return stack
Boolean IsEmpty(stack)::=
if (stack == CreateS(maxStackSize))
return True
else return False
Element Pop(stack)::=
if (IsEmpty(stack)) return
else 移除頂端元素並 return
```
### 3. Stack implement
#### 3.1 Implement of ADT
> The following code was saved in `stackADT.c`.
```c=
/* stackADT.c */
typedef struct{
int key;
}element; /* define element of stack */
void IsFull(int top){
if (top == MAX_STACK_SIZE - 1){
fprintf(stderr, "The stack is FULL.\n");
exit(EXIT_FAILURE);
}
}
void IsEmpty(int top){
if (top < 0){
fprintf(stderr, "The stack is EMPTY.\n");
exit(EXIT_FAILURE);
}
}
void push(int *top, element item, element stack[]){
IsFull(*top);
stack[++(*top)] = item; /* top plus 1 then save new item */
}
element pop(int *top, element stack[]){
IsEmpty(*top);
return stack[(*top)--]; /* return item then top subtract 1 */
}
```
#### 3.2 Stack implement
> The following code was saved in `basic_stack.c`.
```c=
/* basic_stack.c */
#include <stdio.h>
#include "stackADT.h"
/* MAX_STACK_SIZE = 3 */
int main (void){
element stack[MAX_STACK_SIZE]; /* create a stack with 3 positions */
element year = {1995};
element month = {11};
element date = {20};
element item;
int top = -1;
int i;
/* push 3 elements */
push(&top, year, stack);
push(&top, month, stack);
push(&top, date, stack);
for (i = 0; i <= top; i++){
printf("stack[%d] = %d\n", i, stack[i].key);
}
/* pop one element */
item = pop(&top, stack);
printf("poped item = %d\n", item.key);
for (i = 0; i <= top; i++){
printf("stack[%d] = %d\n", i, stack[i].key);
}
return 0;
}
```
## Sec. 3.2 Dynamic stack
### 1. Introduction to dynamic stack
前述方式使用 1-D array 實作 stack 時有一個缺點，必須在程式編譯時**事先定義 stack 的大小**，而且這個大小**不能改變**。但如果使用**動態分配記憶體**的方式來實作 stack 就可避免這個問題，並在需要的時候(stack 填滿時)**適當的增加 stack 的大小**。
實作上需要事先創建一段記憶體空間，並分配給 stack 設置成初始化的大小。以下先簡述 C 語言中有關動態分配記憶體空間的函式。
### 2. Memory allocation
與動態分配記憶體空間有關的函式都定義在標頭檔 `<stdlib.h>` 之中
* `void *malloc(size_t size);`
* 說明
* malloc 為 memory llocation 的縮寫，表示配置一段固定大小的記憶體空間大小，並回傳該空間第一個 byte 的記憶體位址
* 此段記憶體空間不會進行初始化
* 參數與回傳值
* `size` : 記憶體區塊的大小，以 byte 為單位
* 回傳一個指向該記憶體區塊第一個 bytes 的指標，失敗則回傳 `NULL`
:::info
不進行初始化的意思是該段記憶體空間可能包含之前所定義的資料與內容，反之若進行空間的初始化，則該段記憶體空間的值會被清空，通常會設置為 0 (若為整數型態)
:::
```c
#include <stdlib.h>
int *ptr;
/* malloc for 2 methods */
ptr = (int*) malloc(sizeof(int)); /* 動態分配一個記憶體空間並指向整數型態，再分配給指標變數 ptr */
int *p = malloc(sizeof(int)); /* 宣告一個指向整數的指標，並動態分配一段記憶體空間給它 */
free(ptr);
free (p);
```
* `void *calloc(size_t nitems, size_t size);`
* 說明
* 與 `malloc` 作用相同，但此段記憶體空間會進行初始化
* 參數與回傳值
* `nitems` : 要分配的元素個數
* `size` : 每個元素的大小，以 bytes 為單位
* 回傳一個指向該記憶體區塊第一個 byte 的指標，失敗則回傳 `NULL`
```c
#include <stdlib.h>
int *ptr1, *ptr2;
ptr1 = calloc(5, sizeof(int));
ptr2 = malloc(sizeof(int) * 5);
free(ptr1);
free(ptr2);
```
* `void free(void *ptr);`
* 說明
* 釋放使用 `malloc` 或 `calloc` 函式所配置的記憶體空間
* 通常必須與 `malloc` 或 `calloc` 搭配使用，每分配一段記憶體空間使用完後都必須釋放此空間，否則最後會導致空間不足
* 參數
* `*ptr` : 指向該段記憶體空間的指標
* `void *realloc(void *ptr, size_t size);`
* 說明
* 重新調整之前使用 `malloc` 或 `calloc` 所分配的記憶體空間大小
* 如果 `ptr` 原先是空指標，則重新分配一段記憶體空間
* 一般來說，當使用 `realloc` 時，如果記憶體空間足夠的話會直接往後擴充當前 `ptr` 所指向的區塊；如果空間不足時，會重新尋找一塊適當大小的記憶體空間，並會將原來 `ptr` 所指向的位址的數值複製過去新的位址，舊的位址釋放出去
* 參數
* `*ptr` : 原先的指標，同時也是重新分配的記憶體空間指標，如果分配失敗則指向 `NULL`
* `size` : 新的記憶體空間大小，以 byte 為單位，如果大小為 0 則會釋放該記憶體空間並指向空指標 `NULL`
```c
#include <stdlib.h>
int *ptr;
ptr = malloc(sizeof(int) * 5);
ptr = realloc(ptr, sizeof(int) * 10);
free(ptr);
```
##### 動派分配記憶體的巨集定義
往後內容有關記憶體分配的函式，都使用以下所定義的巨集(macro)取代
```c=
#define MALLOC(ptr, size) \
if (!(ptr = malloc(size))) { \
fprintf(stderr, "Insufficient memory"); \
exit(EXIT_FAILURE); \
}
#define REALLOC(ptr, size) \
if (!(ptr = realloc(ptr, size))) { \
fprintf(stderr, "Insufficient memory"); \
exit(EXIT_FAILURE); \
}
```
### 3. Dynamic stack implement
#### 3.1 Expand memory space
重新設計函式 `IsFULL()` 與 `push()`，當 stack 的空間塞滿時(`top == capacity - 1`)，將空間(`capacity`)擴大為原來的 2 倍。
> The following code is modified from `stackADT.c`.
```c=
void stackFULL(int top, int *capacity, element stack[]){
if (top == (*capacity - 1)){
REALLOC(stack, 2 * (*capacity) * sizeof(element));
*capacity *= 2;
}
}
void dynamic_push(int *top, int *capacity, element item, element stack[]){
stackFULL(*top, capacity, stack);
stack[++(*top)] = item;
}
```
#### 3.2 Implement of dynamic stack
> The following code was saved in `dynamic_stack.c`.
```c=
/* dynamic_stack.c */
#include <stdio.h>
#include <stdlib.h>
#include "stackADT.h"
void main(){
element *stack;
element year = {1995}, month = {11}, date = {20};
element month2 = {10}, date2 = {19};
int top = -1;
int i;
int capacity = 3;
MALLOC(stack, capacity * sizeof(element)); /* allocate memory space for stack */
/* push 3 elements */
dynamic_push(&top, &capacity, year, stack);
dynamic_push(&top, &capacity, month, stack);
dynamic_push(&top, &capacity, date, stack);
for (i = 0; i <= top; i++){
printf("stack[%d] = %d\n", i, stack[i].key);
}
/* stack is FULL, then expand it */
printf("capacity = %d\n", capacity); /* capacity = 3 */
dynamic_push(&top, &capacity, month2, stack); /* capacity = 6 */
dynamic_push(&top, &capacity, date2, stack); /* capacity = 6 */
for (i = 0; i <= top; i++){
printf("stack[%d] = %d\n", i, stack[i].key);
}
printf("capacity = %d\n", capacity); /* capacity = 6 */
free(stack);
}
```
## Sec. 3.3 Queue
### 1. Introduction to queue
佇列(queue)與 stack 一樣都是一種**有序串列的容器**，兩者差別在於 queue 的**插入(add)與刪除(delete)是在==不同端==進行的**，**插入(add)是在後端(rear)** 進行，**刪除(delete)是在前端(front)** 進行。
給定一個空的 queue Q，初始狀態時 front 與 rear 都會指向 -1，表示 Q 是一個**空的 queue**，將 10、3、41、70 依序添加到 Q 中可得
$$
Q = \{10,\ 3,\ 41,\ 70\}
$$
如下圖左，此時 front = 0 會指向 10，rear = 3 會指向 70。再將 10 與 3 依序刪除後可得
$$
Q = \{41,\ 70,\ 11\}
$$
如下圖右，此時 front = 3 會指向 41，rear = 4 會指向 11。
從上述 queue 進行插入與刪除的過程可以發現，==**最先被新增的元素會最先被刪除**==，符合先進先出(**F**irst-**I**n-**F**irst-**O**ut, FIFO)的規則
### 2. ADT of queue
在 queue 的實作中，同樣可以使用一個長度為 n 的一維陣列 `queue[n]` 來表示可存放 n 個元素的 queue，並使用兩個變數 `front` 與 `rear` 來表示指向 front 端與 rear 端的指標。
```
ADT of Queue
Object : a ordered list including zero or numerous elements
Operation :
Queue CreateQ(maxQueueSize)
Boolean IsFullQ(queue, maxQueueSize)::=
if (element number == macQueueSize)
return True
else return False
Queue Add Q(queue, item)::=
if (IsFull(queue)) return queue full
else
add item into queue
return queue
Boolean IsEmptyQ(queue)::=
if (queue == CerateQ(maxQueueSize))
return True
else return False
Element DeleteQ(queue)::=
if (IsEmpty(queue)) return
else
delete element
return element
```
### 3. Queue implement
#### 3.1 Implement of ADT
> The following code was saved in `queueADT.c`
```c=
/* queueADT.c */
typedef struct{
int key;
}element ; /* define element of queue */
void IsFULL(int rear){
if (rear == (MAX_QUEUE_SIZE - 1)){
fprintf(stderr, "The queue is FULL.\n");
exit(EXIT_FAILURE);
}
}
/*
* There are two methods to judge if queue is EMPTY:
* (1) When front = -1 or rear = -1, queue is EMPTY.
* (2) When rear > front, queue is FULL.
*/
void IsEMPTY(int front, int rear){
if ((front < 0) || (front > rear)){
fprintf(stderr, "The queue is EMPTY.\n");
exit(EXIT_FAILURE);
}
}
void addq(int *front, int *rear, element item, element queue[]){
IsFULL(*rear);
queue[++(*rear)] = item;
/* if insert the first item, then initialize front */
if ((*front) == -1)
*front = 0;
printf("front = %d, rear = %d\n", *front, *rear);
}
/**
* When delete the last item, queue is EMPTY.
* Then must initialize front and rear to -1.
*/
element deleteq(int *front, int *rear, element queue[]){
element item ;
IsEMPTY(*front, *rear);
item = queue[(*front)++];
/* initialize the queue */
if ((*front) > (*rear)){
*front = -1;
*rear = -1;
}
printf("front = %d, rear = %d\n", *front, *rear);
return item;
}
```
#### 3.2 Implement of queue
> The following code was saved in `basic_queue.c`
```c=
/* basic_queue.c */
#include <stdio.h>
#include <stdlib.h>
#include "queueADT.h"
/* max_queue_size = 3 */
int main(){
element a = {10};
element b = {20};
element c = {30};
element d = {40};
int i;
int rear = -1, front = -1;
element queue[MAX_QUEUE_SIZE]; /* create a queue */
addq(&front, &rear, a, queue); /* front = 0, rear = 0 */
addq(&front, &rear, b, queue); /* front = 0, rear = 1 */
addq(&front, &rear, c, queue); /* front = 0, rear = 2 */
deleteq(&front, &rear, queue); /* front = 1, rear = 2 */
for (i = front; i <= rear; i++){
printf("queue[%d] = %d\n", i, queue[i].key);
}
return 0;
}
```
### 4. Application: job scheduler
Queue 常用在作業系統的工作排程中，如以下工作排程 :
| front | rear | Q[0] | Q[1] | Q[2] | Q[3] | Comments |
| :-: | :-: | :-: | :-: | :-: | :-: | :-: |
| -1 | -1 | | | | | queue is empty |
| -1 | 0 | Job1 | | | | Job1 is added |
| -1 | 1 | Job1 | Job2 | | | Job2 is added |
| -1 | 2 | Job1 | Job2 | Job3 | | Job3 is added |
| 0 | 2 | | Job2 | Job3 | | Job1 is deleted |
| 1 | 2 | | | Job3 | | Job2 is deleted |
但類似上述的線性佇列(linear queue)中，會產生某些問題。例如上面的工作排程中，當 `rear == MAX_QUEUE_SIZE - 1` 時 queue 會被判斷是滿的，但因為 `front != 0` 的關係所以實際上 queue 不是滿的。此時需要把整個 array 往右平移，使得第一個元素的位置在 `queue[0]` 之中，但 array 的移動過程非常耗時。
### 5. Circular queue
為了解決上述 queue 會被誤判為滿的情況，可使用 circular queue(環狀佇列)來進行，如下圖所示。
從上圖的 circular queue 可以歸納出幾件事 :
* 初始化狀況，`rear` 與 `front` 皆設為 0
* 當新增/刪除元素時，`rear` 與 `front` 指標會順時針方向做旋轉
當 queue 滿載(`rear=5`)時，再次新增元素後 `rear` 會指向 0 的位置，也就是說 `MAX_QUEUE_SIZE - 1` 的下一個位置是 `0`，由次可修正 `addq()` 函式中 `rear` 的更新方式
```c
if (rear == MAX_QUEUE_SIZE - 1)
rear = 0; /* back to origin */
else
rear++;
```
上述的寫法也可以等價於 `rear = (rear +１） % MAX_QUEUE_SIZE`
---
此外，在 circular queue 中還會有一個問題。當 `front == rear` 時可以分為兩種狀況
1. queue 是空的，也就是 initialized queue
2. queue 是滿的
為了解決這個問題，當 queue 快要滿載時就擴大 queue 的空間(即動態佇列)，這樣可避免在新增元素時遇到 `front == rear` 的情況。另外也定義 `front == rear` 時 queue 是空的。
若真的要判斷 queue 是不是滿載，可以先判斷 `(rear+1) == front`，如果相等，表示 `rear` 指標往後移動後會與 `front` 重疊，此即 queue 滿載。
#### 5.1 Implement of circular queue add and delete
根據上述的修正方式，可以重新修改新增函式 `addq()` 與 刪除函式 `deleteq()`
> The followinq code is modified from `queueADT.c`
```c=
/* queueADT.c */
void add_cq(int *front, int *rear, element item, element queue[]){
*rear = (*rear + 1) % MAX_QUEUE_SIZE; /* rear plus 1, first */
/* if insert the first item, then initialize front */
if (*front == -1)
*front = 0;
if ((*front == *rear)){ /* if (rear plus 1) equal front, ten queue is full */
fprintf(stderr, "The queue is FULL.\n");
exit(EXIT_FAILURE);
}
queue[*rear] = item;
printf("front = %d, rear = %d\n", *front, *rear);
}
element delete_cq(int *front, int *rear, element queue[]){
element item;
if (*front == *rear){
fprintf(stderr, "The queue is EMPTY.\n");
exit(EXIT_FAILURE);
}
item = queue[*front];
*front = (*front + 1) % MAX_QUEUE_SIZE;
printf("front = %d, rear = %d\n", *front, *rear);
return item;
}
```
#### 5.2 Implement of circular queue
> The following code is save in `basic_cq.c`.
```c=
/* basic_cq.c */
#include <stdio.h>
#include <stdlib.h>
#include "queueADT.h"
int main(){
element a = {10};
element b = {20};
element c = {30};
element d = {40};
int i;
int rear = -1, front = -1;
element queue[MAX_QUEUE_SIZE]; /* create a queue */
addq(&front, &rear, a, queue); /* front = 0, rear = 0 */
addq(&front, &rear, b, queue); /* front = 0, rear = 1 */
addq(&front, &rear, c, queue); /* front = 0, rear = 2 */
//addq(&front, &rear, d, queue); /* The queue is FULL. */
deleteq(&front, &rear, queue); /* front = 1, rear = 2 */
for (i = front; i <= rear; i++){
printf("queue[%d] = %d\n", i, queue[i].key);
}
return 0;
}
```
## Sec. 3.4 Dynamic queue
### 1. Introduction to dynamic queue
與動態堆疊類似，以變數 `capacity` 表示 queue 中初始化的位置數，當 queue 滿位時再使用 `realloc()` 等函式將容量擴增兩倍，且使用 circular queue 的方法來避免 array 做過多的搬移。
這裡先改變 `front` 變數的使用方式，原先是指向開頭(front)端的元素，在此處將 front 指向開頭端的前一個元素，因此當 circular queue 滿位時，元素個數 = MAX_QUEUE_SIZE - 1，如下圖所示。
:::danger
因為 queue 具有 FIFO 的性質，所以首項的開頭元素必定是 front 端的下一個(順時針方向)，不要被位置編號搞混。
:::
以上圖的例子為例，動態佇列的擴展步驟簡述如下 :
* 將滿載的 cirular queue 攤平後可得一個類似 1-D array 的結構(下圖1)
* 擴大 circular queue 的空間後可得下圖(2)
* 因為擴充後新的元素必須從 rear 端加入，因此將 front 端的 (f, A, B) 往後移動(下圖3)
* 改變元素位置呈現如圖(4)
上述的過程可整理為以下 pseudo code :
* `old_queue[front+1:capaciy-1] -> new_queue[start at 0]`
* `old_queue[0:rear] -> new_queue[start at capacity-front-1]`
此外，在進行 array 中 front 端移動位置時尚需考慮兩種狀況 : (1) 若攤平後的 queue 沒有捲繞(下圖1)，則直接擴大容量。(2) 若攤平後的 queue 有捲繞(下圖2)，則需要進行搬移。
### 2. Implement of circular queue
#### 2.1 Expand memory space
重新設計函式 `IsFULL()`，針對 circular queue 的部分也重新設計函式 `add_cq()` 與 `delete_cq()`。當 `(rear+1) % (capacity) == front` 時表示 circular queue 滿載，並將空間(`capacity`)擴大為 2 倍。
函式 `copy()` 是對陣列的搬移複製，將 old_array 中 a 到 b 的內容複製到 new_array 從 c 開始的位置。
> The following code is modified from `queueADT.c`.
```c=
/* queueADT.c */
void copy(int a, int b, int c, element old_queue[], element new_queue[]){
int i, length;
length = (b - a) + 1;
for (i = 0; i < length; i++){
new_queue[c+i] = old_queue[a+i];
}
}
void queueFULL(int *front, int *rear, int *capacity, element **queue){
int start;
element *new_queue;
MALLOC(new_queue, 2 * (*capacity) * sizeof(element));
start = (*front + 1) % (*capacity); /* the first element in old_queue */
if (start < 2){
copy(start, *rear, 0, *queue, new_queue);
}
else{
copy(start, *capacity-1, 0, *queue, new_queue);
copy(0, *rear, (*capacity) - (*front) - 1, *queue, new_queue);
}
*rear = *capacity - 2;
*front = (*capacity) * 2 - 1;
*capacity *= 2;
free(*queue);
*queue = new_queue;
}
void dynamic_addq(int *front, int *rear, int *capacity, element item, element **queue){
int next;
next = (*rear + 1) % (*capacity);
if (next == *front)
queueFULL(front, rear, capacity, queue);
(*queue)[++(*rear)] = item;
printf("front = %d, rear = %d\n", *front, *rear);
}
element dynamic_deleteq(int *front, int *rear, int *capacity, element queue[]){
element item;
if (*front == *rear){
fprintf(stderr, "The queue is EMPTY.\n");
exit(EXIT_FAILURE);
}
*front = (*front + 1) % (*capacity);
item = queue[*front];
printf("front = %d, rear = %d\n", *front, *rear);
return item;
}
```
#### 2.2 Implement of dynamic queue
> The following code is saved in `dynamic_queue.c`.
```c=
/* dynamic_queue.c */
#include <stdio.h>
#include <stdlib.h>
#include "queueADT.h"
int main(){
element a = {10};
element b = {20};
element c = {30};
element d = {40};
int i;
int rear = 0, front = 0;
int capacity = 3;
element *queue;
MALLOC(queue, capacity * sizeof(element));
printf("Original address: %x\n", queue);
dynamic_addq(&front, &rear, &capacity, a, &queue); /* front = 0, rear = 1 */
dynamic_addq(&front, &rear, &capacity, b, &queue); /* front = 0, rear = 2 */
dynamic_addq(&front, &rear, &capacity, c, &queue); /* front = 5, rear = 2 */
dynamic_addq(&front, &rear, &capacity, d, &queue); /* front = 5, rear = 3 */
dynamic_deleteq(&front, &rear, &capacity, queue); /* front = 0, rear = 3 */
dynamic_deleteq(&front, &rear, &capacity, queue); /* front = 1, rear = 3 */
for (i=front+1; i<=rear; i++){
printf("queue[%d] = %d\n", i, queue[i].key);
}
free(queue);
printf("After expand queue: %x\n", queue);
return 0;
}
```
Sign in with Wallet
Connect another wallet