在計算機科學中,棧(Stack)和隊列(Queue)是兩種非常重要的數據結構。它們廣泛應用于各種算法和程序中,如表達式求值、函數調用、任務調度等。本文將詳細介紹如何在C語言中實現棧和隊列,并通過代碼示例幫助讀者理解其工作原理。
棧是一種遵循后進先出(LIFO, Last In First Out)原則的線性數據結構。這意味著最后進入棧的元素將最先被移除。棧的操作主要包括:
在C語言中,??梢酝ㄟ^數組或鏈表來實現。下面我們將分別介紹這兩種實現方式。
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX_SIZE 100
typedef struct {
int data[MAX_SIZE];
int top;
} Stack;
// 初始化棧
void initStack(Stack *s) {
s->top = -1;
}
// 判斷棧是否為空
bool isEmpty(Stack *s) {
return s->top == -1;
}
// 判斷棧是否已滿
bool isFull(Stack *s) {
return s->top == MAX_SIZE - 1;
}
// 入棧
void push(Stack *s, int value) {
if (isFull(s)) {
printf("棧已滿,無法入棧\n");
return;
}
s->data[++s->top] = value;
}
// 出棧
int pop(Stack *s) {
if (isEmpty(s)) {
printf("棧為空,無法出棧\n");
exit(EXIT_FLURE);
}
return s->data[s->top--];
}
// 查看棧頂元素
int peek(Stack *s) {
if (isEmpty(s)) {
printf("棧為空,無法查看棧頂元素\n");
exit(EXIT_FLURE);
}
return s->data[s->top];
}
int main() {
Stack s;
initStack(&s);
push(&s, 10);
push(&s, 20);
push(&s, 30);
printf("棧頂元素: %d\n", peek(&s));
printf("出棧元素: %d\n", pop(&s));
printf("出棧元素: %d\n", pop(&s));
printf("棧頂元素: %d\n", peek(&s));
return 0;
}
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
typedef struct Node {
int data;
struct Node *next;
} Node;
typedef struct {
Node *top;
} Stack;
// 初始化棧
void initStack(Stack *s) {
s->top = NULL;
}
// 判斷棧是否為空
bool isEmpty(Stack *s) {
return s->top == NULL;
}
// 入棧
void push(Stack *s, int value) {
Node *newNode = (Node *)malloc(sizeof(Node));
if (newNode == NULL) {
printf("內存分配失敗\n");
exit(EXIT_FLURE);
}
newNode->data = value;
newNode->next = s->top;
s->top = newNode;
}
// 出棧
int pop(Stack *s) {
if (isEmpty(s)) {
printf("棧為空,無法出棧\n");
exit(EXIT_FLURE);
}
Node *temp = s->top;
int value = temp->data;
s->top = temp->next;
free(temp);
return value;
}
// 查看棧頂元素
int peek(Stack *s) {
if (isEmpty(s)) {
printf("棧為空,無法查看棧頂元素\n");
exit(EXIT_FLURE);
}
return s->top->data;
}
int main() {
Stack s;
initStack(&s);
push(&s, 10);
push(&s, 20);
push(&s, 30);
printf("棧頂元素: %d\n", peek(&s));
printf("出棧元素: %d\n", pop(&s));
printf("出棧元素: %d\n", pop(&s));
printf("棧頂元素: %d\n", peek(&s));
return 0;
}
棧在計算機科學中有廣泛的應用,例如:
隊列是一種遵循先進先出(FIFO, First In First Out)原則的線性數據結構。這意味著最先進入隊列的元素將最先被移除。隊列的操作主要包括:
在C語言中,隊列可以通過數組或鏈表來實現。下面我們將分別介紹這兩種實現方式。
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX_SIZE 100
typedef struct {
int data[MAX_SIZE];
int front;
int rear;
} Queue;
// 初始化隊列
void initQueue(Queue *q) {
q->front = -1;
q->rear = -1;
}
// 判斷隊列是否為空
bool isEmpty(Queue *q) {
return q->front == -1 && q->rear == -1;
}
// 判斷隊列是否已滿
bool isFull(Queue *q) {
return (q->rear + 1) % MAX_SIZE == q->front;
}
// 入隊
void enqueue(Queue *q, int value) {
if (isFull(q)) {
printf("隊列已滿,無法入隊\n");
return;
}
if (isEmpty(q)) {
q->front = 0;
}
q->rear = (q->rear + 1) % MAX_SIZE;
q->data[q->rear] = value;
}
// 出隊
int dequeue(Queue *q) {
if (isEmpty(q)) {
printf("隊列為空,無法出隊\n");
exit(EXIT_FLURE);
}
int value = q->data[q->front];
if (q->front == q->rear) {
q->front = q->rear = -1;
} else {
q->front = (q->front + 1) % MAX_SIZE;
}
return value;
}
// 查看隊頭元素
int peek(Queue *q) {
if (isEmpty(q)) {
printf("隊列為空,無法查看隊頭元素\n");
exit(EXIT_FLURE);
}
return q->data[q->front];
}
int main() {
Queue q;
initQueue(&q);
enqueue(&q, 10);
enqueue(&q, 20);
enqueue(&q, 30);
printf("隊頭元素: %d\n", peek(&q));
printf("出隊元素: %d\n", dequeue(&q));
printf("出隊元素: %d\n", dequeue(&q));
printf("隊頭元素: %d\n", peek(&q));
return 0;
}
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
typedef struct Node {
int data;
struct Node *next;
} Node;
typedef struct {
Node *front;
Node *rear;
} Queue;
// 初始化隊列
void initQueue(Queue *q) {
q->front = NULL;
q->rear = NULL;
}
// 判斷隊列是否為空
bool isEmpty(Queue *q) {
return q->front == NULL;
}
// 入隊
void enqueue(Queue *q, int value) {
Node *newNode = (Node *)malloc(sizeof(Node));
if (newNode == NULL) {
printf("內存分配失敗\n");
exit(EXIT_FLURE);
}
newNode->data = value;
newNode->next = NULL;
if (isEmpty(q)) {
q->front = q->rear = newNode;
} else {
q->rear->next = newNode;
q->rear = newNode;
}
}
// 出隊
int dequeue(Queue *q) {
if (isEmpty(q)) {
printf("隊列為空,無法出隊\n");
exit(EXIT_FLURE);
}
Node *temp = q->front;
int value = temp->data;
q->front = temp->next;
if (q->front == NULL) {
q->rear = NULL;
}
free(temp);
return value;
}
// 查看隊頭元素
int peek(Queue *q) {
if (isEmpty(q)) {
printf("隊列為空,無法查看隊頭元素\n");
exit(EXIT_FLURE);
}
return q->front->data;
}
int main() {
Queue q;
initQueue(&q);
enqueue(&q, 10);
enqueue(&q, 20);
enqueue(&q, 30);
printf("隊頭元素: %d\n", peek(&q));
printf("出隊元素: %d\n", dequeue(&q));
printf("出隊元素: %d\n", dequeue(&q));
printf("隊頭元素: %d\n", peek(&q));
return 0;
}
隊列在計算機科學中也有廣泛的應用,例如:
棧和隊列雖然都是線性數據結構,但它們的操作方式和應用場景有所不同:
操作方式:
應用場景:
棧和隊列是計算機科學中最基本的數據結構之一,理解它們的實現原理和應用場景對于編寫高效的程序至關重要。本文通過C語言代碼示例詳細介紹了如何使用數組和鏈表實現棧和隊列,并探討了它們的應用場景。希望本文能幫助讀者更好地理解和掌握這兩種數據結構。
免責聲明:本站發布的內容(圖片、視頻和文字)以原創、轉載和分享為主,文章觀點不代表本網站立場,如果涉及侵權請聯系站長郵箱:is@yisu.com進行舉報,并提供相關證據,一經查實,將立刻刪除涉嫌侵權內容。