一、题目描述
请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(push
、top
、pop
和empty
)。
实现MyStack
类:
void push(int x)
将元素x
压入栈顶。int pop()
移除并返回栈顶元素。int top()
返回栈顶元素。boolean empty()
如果栈是空的,返回true
;否则,返回false
。
大约 2 分钟
请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(push
、top
、pop
和empty
)。
实现MyStack
类:
void push(int x)
将元素x
压入栈顶。int pop()
移除并返回栈顶元素。int top()
返回栈顶元素。boolean empty()
如果栈是空的,返回true
;否则,返回false
。请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(push
、pop
、peek
、empty
)。
实现MyQueue
类:
void push(int x)
将元素x
推到队列的末尾int pop()
从队列的开头移除并返回元素int peek()
返回队列开头的元素boolean empty()
如果队列为空,返回true
;否则,返回false
你可以选择使用单链表或者双链表,设计并实现自己的链表。
单链表中的节点应该具备两个属性:val
和next
。val
是当前节点的值,next
是指向下一个节点的指针/引用。
如果是双向链表,则还需要属性prev
以指示链表中的上一个节点。假设链表中的所有节点下标从0开始。
实现MyLinkedList类:
MyLinkedList()
初始化MyLinkedList
对象。int get(int index)
获取链表中下标为index
的节点的值。如果下标无效,则返回-1。void addAtHead(int val)
将一个值为val
的节点插入到链表中第一个元素之前。在插入完成后,新节点会成为链表的第一个节点。void addAtTail(int val)
将一个值为val
的节点追加到链表中作为链表的最后一个元素。void addAtIndex(int index, int val)
将一个值为val
的节点插入到链表中下标为index
的节点之前。如果index
等于链表的长度,那么该节点会被追加到链表的末尾。如果index
比长度更大,该节点将不会插入到链表中。void deleteAtIndex(int index)
如果下标有效,则删除链表中下标为index
的节点。