编写一个能为栈也能为队列的线性表。
时间: 2024-02-06 14:08:50 浏览: 29
可以使用双向链表来实现一个既能作为栈又能作为队列的线性表。
具体实现步骤如下:
1. 定义一个节点结构体,包含元素值、指向前驱节点的指针和指向后继节点的指针。
2. 定义一个链表结构体,包含头节点和尾节点指针,以及链表长度。
3. 实现链表的初始化函数,创建头节点和尾节点,并将它们相互指向,链表长度初始化为0。
4. 实现入栈/队列的操作函数,分别在链表尾部插入新节点。
5. 实现出栈/队列的操作函数,分别在链表头部删除节点。
6. 实现获取栈顶/队首元素的操作函数,返回链表头部节点的值。
7. 实现获取栈/队列长度的操作函数,返回链表长度。
以下是代码实现示例(使用C语言):
```c
typedef struct Node {
int value;
struct Node *prev;
struct Node *next;
} Node;
typedef struct List {
Node *head;
Node *tail;
int length;
} List;
void initList(List *list) {
Node *node = (Node*)malloc(sizeof(Node));
node->prev = NULL;
node->next = NULL;
list->head = node;
list->tail = node;
list->length = 0;
}
void push(List *list, int value) {
Node *node = (Node*)malloc(sizeof(Node));
node->value = value;
node->prev = list->tail;
node->next = NULL;
list->tail->next = node;
list->tail = node;
list->length++;
}
int pop(List *list) {
if (list->length == 0) {
return -1; // 栈/队列为空
}
Node *node = list->head->next;
int value = node->value;
list->head->next = node->next;
if (node->next != NULL) {
node->next->prev = list->head;
} else {
list->tail = list->head;
}
free(node);
list->length--;
return value;
}
int peek(List *list) {
if (list->length == 0) {
return -1; // 栈/队列为空
}
return list->head->next->value;
}
int size(List *list) {
return list->length;
}
```